翻訳と辞書 Words near each other ・ Probe Ridge ・ Probelesodon ・ Proben ・ Probenecid ・ Probenecid and colchicine ・ Probergrothius ・ Probert ・ Proba-V ・ PROBA2 ・ Probabilism ・ Probabilist ・ Probabilistic analysis of algorithms ・ Probabilistic Approach for Protein NMR Assignment Validation ・ Probabilistic argument ・ Probabilistic argumentation ・ Probabilistic automaton ・ Probabilistic bisimulation ・ Probabilistic causation ・ Probabilistic classification ・ Probabilistic CTL ・ Probabilistic data association filter ・ Probabilistic database ・ Probabilistic design ・ Probabilistic encryption ・ Probabilistic forecasting ・ Probabilistic latent semantic analysis ・ Probabilistic logic ・ Probabilistic logic network ・ Probabilistic method ・ Probabilistic metric space Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Probabilistic automaton ： ウィキペディア英語版 Probabilistic automaton In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix or stochastic matrix. Thus, the probabilistic automaton generalizes the concept of a Markov chain or subshift of finite type. The languages recognized by probabilistic automata are called stochastic languages; these include the regular languages as a subset. The number of stochastic languages is uncountable. The concept was introduced by Michael O. Rabin in 1963;〔 〕 a certain special case is sometimes known as the Rabin automaton. In recent years, a variant has been formulated in terms of quantum probabilities, the quantum finite automaton. ==Definition== The probabilistic automaton may be defined as an extension of a non-deterministic finite automaton $(Q,\backslash Sigma,\backslash delta,q\_0,F)$, together with two probabilities: the probability $P$ of a particular state transition taking place, and with the initial state $q\_0$ replaced by a stochastic vector giving the probability of the automaton being in a given initial state. For the ordinary non-deterministic finite automaton, one has * a finite set of states $Q$ * a finite set of input symbols $\backslash Sigma$ * a transition function $\backslash delta:Q\backslash times\backslash Sigma\; \backslash to\; P(Q)$ * a set of states $F$ distinguished as ''accepting'' (or ''final'') ''states'' $F\backslash subset\; Q$. Here, $P(Q)$ denotes the power set of $Q$. By use of currying, the transition function $\backslash delta:Q\backslash times\backslash Sigma\; \backslash to\; P(Q)$ of a non-deterministic finite automaton can be written as a membership function :$\backslash delta:Q\backslash times\backslash Sigma\; \backslash times\; Q\backslash to\; \backslash$ so that $\backslash delta(q,a,q^\backslash prime)=1$ if $q^\backslash prime\backslash in\; \backslash delta(q,a)$ and $\backslash delta(q,a,q^\backslash prime)=0$ if $q^\backslash prime\backslash notin\; \backslash delta(q,a)$. The curried transition function can be understood to be a matrix with matrix entries :$\backslash left()\_=\backslash delta(q,a,q^\backslash prime)$ The matrix $\backslash theta\_a$ is then a square matrix, whose entries are zero or one, indicating whether a transition $q\backslash stackrel\; q^\backslash prime$ is allowed by the NFA. Such a transition matrix is always defined for a non-deterministic finite automaton. The probabilistic automaton replaces this matrix by a stochastic matrix $P$, so that the probability of a transition is given by :$\backslash left()\_$ A state change from some state to any state must occur with probability one, of course, and so one must have :$\backslash sum\_\backslash left()\_=1$ for all input letters $a$ and internal states $q$. The initial state of a probabilistic automaton is given by a row vector $v$, whose components add to unity: :$\backslash sum\_\backslash left()\_=1$ The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string $abc$, would be :$v\; P\_a\; P\_b\; P\_c$ In particular, the state of a probabilistic automaton is always a stochastic vector, since the product of any two stochastic matrices is a stochastic matrix, and the product of a stochastic vector and a stochastic matrix is again a stochastic vector. This vector is sometimes called the distribution of states, emphasizing that it is a discrete probability distribution. Formally, the definition of a probabilistic automaton does not require the mechanics of the non-deterministic automaton, which may be dispensed with. Formally, a probabilistic automaton ''PA'' is defined as the tuple $(Q,\backslash Sigma,P,\; v,\; F)$. A Rabin automaton is one for which the initial distribution $v$ is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Probabilistic automaton」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.